package com.wk.data;
/**
 * 随机集合 O(1)
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

public class RandomizedSet {
	List<Integer> list = new ArrayList<Integer>();
	Map<Integer, Integer> valToIndex = new HashMap<Integer, Integer>();
	/** 如果 val 不存在集合中，则插入并返回 true，否则直接返回 false */
    public boolean insert(int val) {
    	if(valToIndex.containsKey(val)) {
    		return false;
    	}
    	list.add(val);
    	valToIndex.put(val, list.size()-1);
    	return true;
    }

    /** 如果 val 在集合中，则删除并返回 true，否则直接返回 false */
    public boolean remove(int val) {
    	if(!valToIndex.containsKey(val)) {
    		return false;
    	}
    	int index = valToIndex.get(val);
    	valToIndex.put(list.get(list.size()-1), index);
    	//交换
    	int temp = list.get(index);
    	list.set(index, list.get(list.size()-1));
    	list.set(list.size()-1, temp);
    	list.remove(list.size()-1);
    	valToIndex.remove(val);
    	return true;
    }

    /** 从集合中等概率地随机获得一个元素 */
    public int getRandom() {
    	return list.get(new Random().nextInt(list.size()));
    }
}
